//
// Created by Administrator on 2021/5/19.
//
//给你一个n x n矩阵matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
//请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。
//
//
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#include <vector>
#include <iostream>
#include <queue>
using namespace std;

class Solution {
public:
    int kthSmallest(vector<vector<int>> &matrix, int k) {
        /**
         * 二维化一维  排序或者优先队列都可以  没有利用到矩阵的性质
         */
        priority_queue<int> ans;
        for (auto &x:matrix) {
            for (auto &y:x) {
                ans.push(y);
                if (ans.size() > k) ans.pop();
            }
        }
        return ans.top();
    }
};
class Solution2 { // 题解 归并排序 利用了一维有序的性质
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        struct point {
            int val, x, y;
            point(int val, int x, int y) : val(val), x(x), y(y) {};
            bool operator> (const point& a) const { return this->val > a.val; }
        };
        priority_queue<point, vector<point>, greater<>> que; // 小堆顶
        int n = (int)matrix.size();
        for (int i = 0; i < n; i++) {
            que.emplace(matrix[i][0], i, 0); // 第一列
        }
        for (int i = 0; i < k - 1; i++) {
            point now = que.top();
            que.pop();
            if (now.y != n - 1) { // 不到最后一列
                que.emplace(matrix[now.x][now.y + 1], now.x, now.y + 1);
            }
        }
        return que.top().val;
    }
};
class Solution3 {  // 二分 利用两重有序性质
public:
    bool check(vector<vector<int>>& matrix, int mid, int k, int n) {
        int i = n - 1; // 从左下角开始
        int j = 0;
        int num = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] <= mid) {
                num += i + 1;
                j++;
            } else {
                i--;
            }
        }
        return num >= k;
    }

    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = (int)matrix.size();
        int left = matrix[0][0];
        int right = matrix[n - 1][n - 1];
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (check(matrix, mid, k, n)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

int main() {
    vector<vector<int>> mat{{1,  5,  9},
                            {10, 11, 13},
                            {12, 13, 15}};
    Solution3 sol;
    cout << sol.kthSmallest(mat, 8) << endl;
    return 0;
}